package 中等.链表;

import java.util.ArrayList;
import java.util.List;

/**
 * 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。
 * val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性
 *  prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
 * 在链表类中实现这些功能：
 * get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
 * <p>
 * addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插
 * 入后，新节点将成为链表的第一个节点。
 * <p>
 * addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
 * <p>
 * addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 
 * 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果
 * index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
 * <p>
 * deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/design-linked-list
 */
public class 设计链表_707 {

    public static void main(String[] args) {

        MyLinkedList linkedList = new MyLinkedList();

        linkedList.addAtHead(2);
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        System.out.println(linkedList.get(2));

        linkedList.deleteAtIndex(1);
        System.out.println(linkedList.get(1));

        linkedList.addAtIndex(1, 2);
        System.out.println(linkedList.get(1));

        List<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(0, 1);
        System.out.println(list);

    }

    /**
     * 双向链表
     * 注意：索引 index 是从 0 开始的
     */
    static class MyLinkedList {

        // 虚拟头尾节点
        private Node head = new Node(0);

        private Node tail = new Node(0);

        private int size = 0;


        public MyLinkedList() {
            // 连接虚拟头尾节点
            head.next = tail;
            tail.pre = head;
        }

        public int get(int index) {
            Node node = getNode(index);
            return node != null ? node.val : -1;
        }

        private Node getNode(int index) {
            if (index >= size) {
                return null;
            }
            Node curNode = head;
            while (index >= 0 && curNode.next.next != null) {
                curNode = curNode.next;
                index--;
            }
            return index < 0 ? curNode : null;
        }

        public void addAtHead(int val) {
            Node addNode = new Node(val);
            addNode.pre = head;
            addNode.next = head.next;
            head.next.pre = addNode;
            head.next = addNode;

            size++;
        }

        public void addAtTail(int val) {
            Node addNode = new Node(val);
            addNode.pre = tail.pre;
            addNode.next = tail;
            tail.pre.next = addNode;
            tail.pre = addNode;

            size++;
        }

        public void addAtIndex(int index, int val) {
            if (index < 0) {
                addAtHead(val);
            } else if (index == size) {
                addAtTail(val);
            } else if (index < size) {
                Node node = getNode(index);
                Node addNode = new Node(val);
                addNode.pre = node.pre;
                addNode.next = node;
                node.pre.next = addNode;
                node.pre = addNode;
                size++;
            }
        }

        public void deleteAtIndex(int index) {
            Node delNode = getNode(index);
            if (delNode != null) {
                delNode.pre.next = delNode.next;
                delNode.next.pre = delNode.pre;
                size--;
            }
        }

        class Node {
            private int val;

            private Node pre;

            private Node next;

            public Node(int val) {
                this.val = val;
            }
        }
    }

}
